package leetcode.Fiftyone_to_One_hundred;

/**
 * 反转链表 II
 *
 * 解题关键是：pre 一旦找到正确的位置后就不能改变了
 */
public class Test92 {

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static ListNode reverseBetween(ListNode head, int m, int n) {
        // 根据T206的解法，首先将 pre 定位到需要更改的第一个节点的前一个
        ListNode temp = new ListNode(0);
        temp.next = head;
        ListNode pre = temp;
        for(int i = 1; i < m; i++){
            pre = pre.next;
        }
        // 同理 cur 定位到第一个要更改的节点
        ListNode cur = pre.next;
        for(int i = m; i < n; i++){
            // 同理 next 定位到第一个 next 位置
            ListNode next = cur.next;

            cur.next = next.next;
            next.next = pre.next;
            // 将断开的链表重连
            pre.next = next;
        }
        return temp.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        ListNode ans =  reverseBetween(l1, 2, 4);
        while (ans != null) {
            System.out.print(ans.val);
            ans = ans.next;
        }
    }
}
